package com.tgy.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/9/20 9:50 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 */
public class _121_买卖股票的最佳时机_01 {

    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }

       int maxProfix = 0;

        Deque<Integer> deque = new LinkedList<>();
//
        for (int i = 0; i <= prices.length; i++) {

            // 为数组最后一个元素添加0
           int price = (i == prices.length ? 0: prices[i]);

            while (!deque.isEmpty() && deque.peek() > price) {

                maxProfix = Math.max(deque.peek() - deque.peekLast(),maxProfix);
                deque.pollFirst();
            }

            deque.addFirst(price);
        }

        return maxProfix;
    }

    public int maxProfit01(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }

        int maxProfix = 0;

        Deque<Integer> deque = new LinkedList<>();
        deque.offer(prices[0]);

        // 为数组最后一个元素添加0
        int[] nPrices = new int[prices.length + 1];
        for (int i = 0; i < prices.length; i++) {

            nPrices[i] = prices[i];
        }


        int index = 1;
        while (!deque.isEmpty() && index < nPrices.length) {


            while (index < nPrices.length - 1 && deque.peek() <= nPrices[index]) {

                deque.addFirst(nPrices[index++]);
            }



            int val = nPrices[index++];

            while (!deque.isEmpty() && deque.peek() > val) {

                Integer topVal = deque.poll();

                if (!deque.isEmpty() && (topVal - deque.peekLast()) > maxProfix) {

                    maxProfix = (topVal - deque.peekLast());
                }
            }

            deque.addFirst(val);
        }


        return maxProfix;
    }
}
